The present invention relates to a novel method of protecting broadcast data, especially encrypted audiovisual broadcast programs. More particularly, the present invention relates to a novel method of protecting broadcast programs by utilizing a novel technique of fingerprinting a common decryption function in broadcast systems.
Movies, music and software are often distributed in digital form to paying customers.
Since digital data can be easily stored and redistributed without any loss of quality, there is a real danger that some of these customers will give away or sell the data to other recipients, and thus hurt the revenue stream of the copyright holder.
A well known technique to discourage such piracy is to modify the data sent to each paying customer in a way which does not affect its intended purpose (i.e., it is not visible in images, it is not audible in music, and it does not affect the behavior of software). The copies 15 sent to the various customers are functionally identical, but each copy contains a unique hidden fingerprint, which can be extracted only by the sender who knows some secret key.
These fingerprints can be used to automate the process of scanning large databases (such as the internet) for stolen electronic property, to identify the misbehaving customer, and to prove his involvement in court.
To be useful, fingerprints should be hard to modify or to eliminate. Since they are likely to be generated by commercially available systems, we have to assume that the pirate knows the general nature of the fingerprinting scheme, but not the secret keys used by the sender to generate particular fingerprints. For example, an image can be marked by embedding the identity of the broadcaster and the customer in the least significant bits of the numbers representing the luminance of particular pixels. Such a subtle modification does not degrade the aesthetic value of the image and is not likely to be detectable by visual inspection, but it can be easily extracted from the image file by a program that knows where to look and what to look for.
Unfortunately, pirates can often defeat fingerprinting schemes by applying additional modifications. For example, the pirate can randomize the low order bits of all the pixels in the image, and thus eliminate the fingerprint even if he does not know where it was embedded. Another common technique is to crop, reduce, rotate, compress or rescan the image in order to change the actual location and value of various pixels in the image file. An even more powerful attack is to obtain several copies of the same image (with different fingerprints), and then to analyze and eliminate all the differences between them. A small group of colluding pirates (each posing as a legitimate customer) can often compute a new mixed image file which cannot be traced to any one of them.
The definition of the problem that this invention deals with is a special case of the general fingerprinting problem, in which the object to be fingerprinted is an algorithm for computing some function. It is motivated by the common practice of protecting audiovisual programs broadcast via cable or satellite by encrypting them and giving each paying customer the corresponding decryption algorithm. Typical pay-TV systems have millions of customers, and thus, it is impractical to send each customer a different encrypted version of the program. Instead, the sender broadcasts one encrypted version of the program, and all the customers use the same decryption function to gain access to the program.
The main security problem in such a scheme is that anyone who knows the common decryption algorithm can sell it to other customers, and thus, enable them to watch the programs without paying the broadcaster. This is particularly problematic when the common decryption algorithm is provided in the form of a software program which is executed in a set top box or in a personal computer. To make this more difficult, broadcasters usually provide the decryption algoritm embedded in a high security microprocessor, such as, a smart card. However, the financial rewards of piracy are so high that commercial pirates spend a lot of time and money on reverse engineering their smart cards. Eventually, they manage to extract the decryption algorithm, and sell it to other customers in the form of pirate cards, emulators, or computer programs.
The principal object of the present invention is, in effect, to watermark or fingerprint the decryption algorithms given to the various customers, in order to track (and then sue) the customer whose smart card was duplicated. As stated before, all the decryption algorithms should implement the same decryption function, but each one of them should be traceable to a particular customer.
A naive implementation of this idea is to use simple algorithmic modifications which have no effect on the result of the computation. For example, one can add dummy variables, exchange the order of unrelated computations, or add pairs of inverse operations, and thus generate millions of algorithms which are functionally equivalent but syntactically different. However, a clever pirate can extract the algorithm from his smart card, study it carefully, and then rewrite it in a totally different way in order to make the pirated copies untraceable. Again, this can be made much easier if the pirate extracts several algorithms from several smart cards, studies their differences, and creates a hybrid version by cutting and pasting modified pieces from the various versions.
To prevent such attacks, an object of the invention is to make the process of modifying one algorithmic representation of the function into another fundamentally different algorithmic representation difficult in some demonstrable way. The pirate can completely rewrite the program he extracts from his smart card, but careful examination of his modified program should reveal some unique feature of the variant he was trying to simulate. This difficulty should only apply to the pirate, whereas the broadcaster (who knows some additional secret information) should not have any difficulty in generating a large number of computationally isolated variants.
One particular scheme of this type was described in a recent paper by Naccache, Shamir and Stem (citation). It deals with the particular class of RSA decryption functions f(x)=x d (mod n), where d is the secret decryption exponent and n is the product of two secret primes p and q. The main observation is that d can be replaced by any exponent d.sub.i of the form d.sub.i =d+i*(p-1)*(q-1), without affecting the functional behaviour of the function f(x). On the other hand, the ability to find any pair of exponents (d.sub.i, d.sub.j) with this property is equivalent to the factorization of n, which is believed to be a very difficult computational task. Thus, each customer can be given a different exponent d.sub.i from this sequence, and the pirate would not be able to replace one d.sub.i he extracts from his card by any equivalent exponent d.sub.j unless he can factor n. The pirate can try to hide the value of d.sub.i by performing the modular exponentiation operation in a convoluted way, but a sufficiently careful examination of the exponentiation code would reveal which exponent was used in the emulation.
However, in its simplest form this idea has serious practical drawbacks:
(a) The modular exponentiation function is too slow when implemented in software on standard smart cards. PA1 (b) The modulus n can be factored if two different exponents are extracted from two smart cards by colluding pirates. PA1 (c) The modulus can be factored in public key applications in which the pirate knows both the public encryption exponent e and the decryption exponent d.sub.i he extracted from his smart card.
The present invention overcomes these difficulties in the context of broadcast systems, in which the function is only applied to particular inputs which are chosen by the broadcaster and revealed to all the customers over a long period of time. The main characteristic of such schemes is that the pirate has to commit to his version of the decryption algorithm when he sells it to his customers, and cannot predict on which inputs his function will be evaluated (except for those which had already been publicly broadcast so far).
The new scheme does not depend on the special properties of particular functions, such as modular exponentiation. It can be based on any standard hash algorithm, such as SHA or MD5. In fact, the only property it uses is that it is difficult to predict the output of the function without actually applying it to its input. In particular, it is of no care or concern whether it is difficult to find collisions, and thus, one can use simplified versions of hash functions, pseudo random functions, or encryption functions in order to make them more suitable to smart cards.
The basic idea of the new scheme is to let each customer evaluate a completely different function, keyed by his unique key k. A simple way to achieve this is to let each customer apply a common hash function h to the concatenation of his unique key k and the given input x, but there are many additional ways to achieve this goal. However, we also have to guarantee that all the customers should get the same results when applying their unique functions to the common broadcast input. The broadcaster achieves this by choosing in advance the sequence X=(x.sub.1, . . . , x.sub.n) of the values he will actually broadcast, and giving each customer a unique precomputed modification table T=(t.sub.1, . . . , t.sub.n) (which typically contains the XOR's or differences between the computed and desired values). By using these values, each customer can derive the common value by a unique local computation, and use it to decrypt the broadcast audiovisual program.
Accordingly, the new method and scheme makes the fingerprinted algorithmic representations only partially equivalent; all the variants behave identically for inputs in some set X, and differently (with high probability) for inputs which are not in X. The broadcaster knows X, and uses only elements from X as inputs in the actual decryption process, in order to guarantee that all his customers perform the same decryption function. However, the pirate cannot find X even by analyzing a large number of variants extracted from multiple smart cards, and the unique behavior of the variant he sells on arbitrary inputs will expose his identity.
Other and further objects and advantages of the present invention will become more readily apparent from the following detailed description of preferred embodiments of the invention, when taken in conjunction with the drawings.